package com.summer.study.leetcode.tree;


import com.summer.study.leetcode.tree.enums.DfsSearchType;
import com.summer.study.leetcode.tree.enums.TraverseType;
import lombok.Data;

import java.util.*;

/**
 * @auther: 杨杰
 * @date: 2019/7/30 10:07
 * @description: 二叉树
 */
@Data
public class BinaryTree<E> extends AbstractTree<E> {

    private BinaryTreeNode root;

    private int size;

    private int height;

    public BinaryTree() {
        size = 0;
        height = 0;
    }

    @Override
    public void init(Node<E> root) {
        if (!(root instanceof BinaryTreeNode)) {
            throw new ClassCastException();
        } else if (getRoot() != null) {
            throw new NullPointerException("根结点已经初始化过了");
        } else {
            setRoot(root);
        }
    }

    @Override
    public boolean insert(Node<E> node, Node<E> parent) {
        boolean flag = false;
        if (parent == null || node == null || (!(node instanceof BinaryTreeNode && parent instanceof BinaryTreeNode))) {
            return flag;
        } else if (((BinaryTreeNode<E>) parent).getLeft() == null) {
            ((BinaryTreeNode<E>) parent).setLeft((BinaryTreeNode<E>) node);
            flag = true;
        } else if (((BinaryTreeNode<E>) parent).getRight() == null) {
            ((BinaryTreeNode<E>) parent).setRight((BinaryTreeNode<E>) node);
            flag = true;
        }
        return flag;
    }

    @Override
    public Node getRoot() {
        return root;
    }


    @Override
    public boolean isLeaf(Node<E> node) {
        boolean flag = false;
        if (node == null || (!(node instanceof BinaryTreeNode))) {
            return flag;
        } else if (((BinaryTreeNode<E>) node).getLeft() != null || ((BinaryTreeNode<E>) node).getRight() != null) {
            flag = true;
        }
        return flag;
    }

    @Override
    public long depth(boolean isMax) {
        return isMax ? maxDepth(root) : minDepth(root);
    }

    @Override
    public boolean setRoot(Node<E> node) {
        if (root == null) {
            root = (BinaryTreeNode) node;
            return true;
        }
        return false;
    }

    @Override
    public List<Node<E>> inOrder() {
        if (root != null) {
            traverse(TraverseType.INORDER, root);
        }
        return nodeList;
    }

    @Override
    public List<Node<E>> preOrder() {
        if (root != null) {
            traverse(TraverseType.PERORDER, root);
        }
        return nodeList;
    }

    @Override
    public List<Node<E>> afterOrder() {
        if (root != null) {
            traverse(TraverseType.AFTERORDER, root);
        }
        return nodeList;
    }

    /**
     * @auther: 杨杰
     * @date: 2019/7/30 18:05
     * @description 广度优先算法
     */
    @Override
    public List<Node<E>> bfs() {
        bfsByQueue(root);
        return nodeList;
    }

    /**
     * @param type :
     * @auther: 杨杰
     * @date: 2019/7/30 18:05
     * @description 深度优先算法
     */
    @Override
    public List<Node<E>> dfs(DfsSearchType type) {
        if (type.equals(DfsSearchType.STACK)) {
            //使用栈进行深度优先
            dfsByStack(root);
        } else if (type.equals(DfsSearchType.RECURSION)) {
            //使用递归进行深度度优先
            dfsRecursion(root);
        }
        return nodeList;
    }


    /**
     * @param traverseType :
     * @param treeNode     :
     * @auther: 杨杰
     * @date: 2019/7/30 15:48
     * @description 树的递归遍历
     */
    private void traverse(TraverseType traverseType, BinaryTreeNode treeNode) {
        if (treeNode != null) {
            if (traverseType.equals(TraverseType.PERORDER)) {
                nodeList.add(treeNode);
                traverse(traverseType, treeNode.getLeft());
                traverse(traverseType, treeNode.getRight());
            } else if (traverseType.equals(TraverseType.INORDER)) {
                traverse(traverseType, treeNode.getLeft());
                nodeList.add(treeNode);
                traverse(traverseType, treeNode.getRight());
            } else {
                traverse(traverseType, treeNode.getLeft());
                traverse(traverseType, treeNode.getRight());
                nodeList.add(treeNode);
            }
        }
    }

    /**
     * @param root :
     * @auther: 杨杰
     * @date: 2019/7/30 18:06
     * @description 使用队列完成广度优先
     */
    private void bfsByQueue(BinaryTreeNode root) {
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        if (root == null) {
            return;
        } else {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            //创建cur的目的是在while循环的时候逐层将树带入，如果直接用root,会导致只能输出一级树
            BinaryTreeNode cur = queue.peek();
            nodeList.add(queue.remove());
            if (cur.getLeft() != null) {
                //先将左分支加入队列，之后先输出
                queue.add(cur.getLeft());
            }
            if (cur.getRight() != null) {
                queue.add(cur.getRight());
            }
        }

    }

    /**
     * @param root :
     * @auther: 杨杰
     * @date: 2019/7/30 18:07
     * @description 使用递归进行深度度优先
     */
    private void dfsRecursion(BinaryTreeNode root) {
        if (root != null) {
            nodeList.add(root);
            dfsRecursion(root.getLeft());
            dfsRecursion(root.getRight());
        }
    }

    /**
     * @param root :
     * @auther: 杨杰
     * @date: 2019/7/30 18:03
     * @description 使用栈完成深度优先搜索
     */
    private void dfsByStack(BinaryTreeNode root) {
        if (root == null) {
            return;
        }
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            BinaryTreeNode temp = stack.peek();
            nodeList.add(stack.pop());
            if (temp.getRight() != null) {
                stack.push(temp.getRight());
            }
            if (temp.getLeft() != null) {
                stack.push(temp.getLeft());
            }
        }
    }


    @Override
    public List<List<E>> levelOrder() {
        return levelOrder(root);
    }

    private List<List<E>> levelOrder(Node root) {
        List<List<E>> levels = new ArrayList<>();
        if (root == null) {
            return levels;
        }
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.add((BinaryTreeNode) root);
        // 2 int level = 0;
        while (!queue.isEmpty()) {
            // 2 levels.add(new ArrayList<E>());
            int level_length = queue.size();
            List<E> currentLevel = new ArrayList<>();
            for (int i = 0; i < level_length; ++i) {
                BinaryTreeNode<E> node = queue.remove();

                // 2 levels.get(level).add(node.getVal());

                currentLevel.add(node.getVal());
                if (node.getLeft() != null) {
                    queue.add(node.getLeft());
                }
                if (node.getRight() != null) {
                    queue.add(node.getRight());
                }
            }
            levels.add(currentLevel);

            //2 level++;
        }
        return levels;
    }

    public static boolean isValidBST(List<Node<Integer>> list) {
        if (list.size() > 2) {
            for (int i = 1; i < list.size() - 1; i++) {
                if (list.get(i - 1).getVal() > list.get(i).getVal()) {
                    return false;
                }
            }
        }
        return true;
    }

    private int maxDepth(BinaryTreeNode<E> node) {
        return node == null ? 0 : 1 + Math.max(maxDepth(node.getLeft()), maxDepth(node.getRight()));
    }

    private int minDepth(BinaryTreeNode<E> node) {
        if (node == null) {
            return 0;
        }
        int left = minDepth(node.getLeft());
        int right = minDepth(node.getRight());
        return Math.min(left, right) + 1;
    }

    @Override
    public boolean isSymmetric() {
        return isMirror(root,root);
    }

    private boolean isMirror(BinaryTreeNode t1, BinaryTreeNode t2) {
        if (t1 == null && t2 == null) {
            return true;
        }
        if (t1 == null || t2 == null) {
            return false;
        }
        return (t1.getVal() == t2.getVal())
                && isMirror(t1.getRight(), t2.getLeft())
                && isMirror(t1.getLeft(), t2.getRight());
    }

}
